package alg20241117;

import java.util.Random;
public class Text {
    public int findKthLargest(int[] nums, int k) {
        int kmax = qsort(0, nums.length - 1, nums, k);
        return kmax;
    }
    public int qsort(int l, int r, int[] nums, int k){
        if(l == r) return nums[l];

        int left = l - 1, right = r + 1, i = l;
        int key = nums[new Random().nextInt((r - l + 1)) + l];
        //将数组分为三区间
        while(i < right){
            if(nums[i] < key) swap(++left, i++, nums);
            else if(nums[i] == key) i++;
            else swap(--right, i, nums);
        }
        //统计三区间的个数
        int b = right - left - 1;
        int c = r - right + 1;
        //递归寻找第k大的数
        if(c >= k) {
            return qsort(right, r, nums, k);
        }else if(b + c >= k){
            return key;
        }else {
            return qsort(l, left, nums, k - b - c);
        }

    }

    public void swap(int i, int j, int[] nums){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
